כל פקודה תתחיל ב-MKגדולות עש מיכאל קלי (Michael Kali), וזאת משתי סיבות:
כדי שבטבלת הקיצורים שבתוך \SpecialChar LyX תופענה כל הפקודות זו לצד זו.
הבחירה דווקא באותיות גדולות נועדה לוודא שהפקודות אינן מתנגשות עם פקודות \SpecialChar LaTeX מקוריות.
על הפקודות להיות קצרות ככל האפשר, וזאת כדי לאפשר את כתיבתן במהירות מבלי ליצור להן קיצור מקלדת. הסיבה לכך שלא ניצור קיצור מקלדת לכל פקודה היא שפעמים רבות ניצור פקודות שתיועדנה למקרים מסוימים מאוד, ואז יעבור זמן רב עד שנשתמש בקיצור המקלדת בפעם הבאה ולכן לא נזכור אותו - הרבה יותר פשוט לזכור את הפקודה שיצרנו מכיוון שיש לה תוכן אמיתי שקשור לפלט הרצוי מן הפקודה. סיבה נוספת היא שיצירת קיצור מקלדת לכל פקודה ולו החריגה ביותר תקשה עלינו ליצור קיצורי מקלדת לפקודות חשובות יותר. לפיכך פקודות שימושיות מאוד שבוודאי ניצור להן קיצור מקלדת ונשתמש בו פעמים רבות אינן צריכות להיות קצרות.
כדי להקל על כתיבת פקודות שלא יצרתי להן קיצור מקלדת כתבתי קיצור מקלדת שיוצר את הקידומת של כל פקודות ה-macrosשלי ואז כל מה שנותר הוא להקיש שלוש-ארבע אותיות כדי לבחור את הפקודה הרצויה, קיצור המקלדת המדובר הוא "Ctrl+k".
לכל גופן יש קידומת בת שתי אותיות.
\(\:\)
\(\:\)קבוצות ופונקציות לפי קורסיםLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\:\)המספרים המרוכבים ופונקציות מרוכבות\(\:\)
\(\newcommand{\MKcis}{\text{cis}}\)\(\cos+i\cdot\sin\). המספרים המרוכבים.
\(\newcommand{\MKre}{\text{Re}}\)החלק הממשי של מספר מרוכב. המספרים המרוכבים.
\(\newcommand{\MKim}{\text{Im}}\)החלק המדומה של מספר מרוכב. המספרים המרוכבים.מופיע גם כתמונה של פונקציה.
\(\:\)גופןmathcal: בסיסים, קבוצת חזקה, העתקות גלואה, המילטוניאן ועוד\(\:\)
\(\newcommand{\MKcla}{\mathcal{A}}\)
\(\newcommand{\MKclb}{\mathcal{B}}\)
\(\newcommand{\MKclc}{\mathcal{C}}\)
\(\newcommand{\MKcld}{\mathcal{D}}\)
\(\newcommand{\MKcle}{\mathcal{E}}\)
\(\newcommand{\MKclf}{\mathcal{F}}\)
\(\newcommand{\MKclg}{\mathcal{G}}\)
\(\newcommand{\MKclh}{\mathcal{H}}\)
\(\newcommand{\MKcli}{\mathcal{I}}\)
\(\newcommand{\MKclj}{J}\)
\(\newcommand{\MKclk}{\mathcal{K}}\)
\(\newcommand{\MKcll}{\mathcal{L}}\)
\(\newcommand{\MKclm}{\mathcal{M}}\)
\(\newcommand{\MKcln}{\mathcal{N}}\)
\(\newcommand{\MKclo}{\mathcal{O}}\)
\(\newcommand{\MKclp}{\mathcal{P}}\)
\(\newcommand{\MKclq}{\mathcal{Q}}\)
\(\newcommand{\MKclr}{\mathcal{R}}\)
\(\newcommand{\MKcls}{\mathcal{S}}\)
\(\newcommand{\MKclt}{\mathcal{T}}\)
\(\newcommand{\MKclu}{\mathcal{U}}\)
\(\newcommand{\MKclv}{\mathcal{V}}\)
\(\newcommand{\MKclw}{\mathcal{W}}\)
\(\newcommand{\MKclx}{\mathcal{X}}\)
\(\newcommand{\MKcly}{\mathcal{Y}}\)
\(\newcommand{\MKclz}{\mathcal{Z}}\)
\(\:\)גופןmathscr: ?\(\:\)
\(\newcommand{\MKsrb}{\mathscr{B}}\)
\(\newcommand{\MKsrf}{\mathscr{F}}\)
\(\:\)גופןmathfrak: אותיות גותיות לעוצמות\(\:\)
\(\newcommand{\MKfka}{\mathfrak{a}}\)
\(\newcommand{\MKfkb}{\mathfrak{b}}\)
\(\newcommand{\MKfkc}{\mathfrak{c}}\)
\(\:\)כתיבת סדרות במהירותLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\newcommand{\MKseq}[3]{#1_{1}#2#1_{2}#2\ldots#2#1_{#3}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKseqz}[3]{#1_{0}#2#1_{1}#2\ldots#2#1_{#3}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKdseq}[5]{#1_{1}#2#3_{1}#4#1_{2}#2#3_{2}#4\ldots#1_{#5}#2#3_{#5}}\)תודה למיכאל קלי שכתב את הפקודה.
\(\newcommand{\MKdseqz}[5]{#1_{0}#2#3_{0}#4#1_{1}#2#3_{1}#4\ldots#1_{#5}#2#3_{#5}}\)תודה למיכאל קלי שכתב את הפקודה.
\fbox{\thepage}\leftmark
התחלקות\fbox{\thepage}
1 יחס החלוקה
1.1 הגדרות
הגדרה 1.1. יהיו \(a,b\in\MKinteger\), נאמר ש-\(a\)מחלק את \(b\) (או ש-\(b\) הוא כפולה של \(a\)) ונסמן \(a\mid b\) אם קיים \(q\in\MKinteger\) כך ש-\(b=a\cdot q\).
\(\clubsuit\)
מהגדרה נובע שאם \(a\mid b\) אז \(a\neq0\).
\(\clubsuit\)
הגדרות שקולות ל-\(\gcd\) ול-\(\MKlcm\) הן:
המחלק המשותף המקסימלי הוא הטבעי הגדול ביותר שמחלק את \(a_{1},a_{2},\ldots,a_{n}\).
הכפולה המשותפת המינימלית היא הטבעי הקטן ביותר שמתחלק ב-\(a_{1},a_{2},\ldots,a_{n}\).
הסיבה להגדרה דווקא בצורה הנ"ל היא שהגדרה זו תופסת בכל חוג חילופי1חוג חילופי (קומוטטיבי) הוא קבוצה שעליה מוגדרות פעולות חיבור וכפל המקיימת את כל אקסיומות השדה מלבד קיום הופכי..
סימון:
לכל \(a\in\MKinteger\) נסמן \(\left(a\right):=a\cdot\MKinteger\) (כזכור \(a\cdot\MKinteger:=\left\{ a\cdot q\mid q\in\MKinteger\right\} \)), כלומר \(\left(a\right)\) היא קבוצת כל הכפולות של \(a\).
\(\clubsuit\)
זוהי ההגדרה של אידיאל בכל חוג חילופי, בחוג השלמים ניתן היה להסתפק בסגירות לחיבור ולחיסור מפני שניתן להמיר כל כפל שלמים לחיבור וחיסור2לעומת זאת אין שום אפשרות להמרת כפל רציונליים בחיבור וזו הסיבה לכך שנזקקנו לשתי פעולות בשדה..
\(\clubsuit\)
בגלל סעיף1משפטים רבים שננסח עבור הטבעיים יהיו נכונים על השלמים בשינויים הקלים המתבקשים.
\(\clubsuit\)
\(r\) זה נקרא השארית של חלוקת \(b\) ב-\(a\) ו-\(q\) נקרא המנה של חלוקה זו.
\(\clubsuit\)
יש לשים לב לכך ש-\(r\) אי-שלילי ולכן השארית של חלוקת \(-8\) ב-\(3\) היא \(1\) ולא \(-2\) כפי שניתן היה לחשוב.
\(\clubsuit\)
לא בכל חוג קיימת חלוקה עם שארית, זהו הבדל מהותי בין חוג השלמים לחוגים אחרים, כך למשל השקילות בין אי-פריקות לראשוניות (שנגיע אליה בהמשך) נובעת ממשפט זה.
\(\clubsuit\)
\(a\) זה נקרא היוצר של האידיאל והוא החיובי הקטן ביותר ששייך לאידיאל.
\(\clubsuit\)
כלומר לכל \(d\in\MKinteger\) מתקיים \(d=\gcd\left(a,b\right)\) אם"ם \(\left(d\right)=\left\{ x\cdot a+y\cdot b\mid x,y\in\MKinteger\right\} \).
\(\clubsuit\)
מכאן נובע שניתן להציג את ה-\(\gcd\) כצר"ל של \(a\) ו-\(b\) ושהוא המספר החיובי הקטן ביותר שניתן להציגו כך.
\(\clubsuit\)
לאפשרות להציג את ה-\(\gcd\) כצר"ל של \(a\) ו-\(b\) ישנה חשיבות רבה בחשבון מודולרי: אם \(a\) ו-\(b\) זרים אז קיימים \(x,y\in\MKinteger\) כך ש-\(1=x\cdot a+y\cdot b\) ומכאן שלכל \(b>c,d\in\MKnatural_{0}\) קיים \(x'\in\MKinteger\) כך ש-\(c\equiv d+x'\cdot a\mod b\) שהרי מתקיים \(x\cdot a=1-y\cdot b\) ומכאן שגם:\[
d+\left(c-d\right)\cdot x\cdot a\equiv d+\left(c-d\right)\cdot\left(1-y\cdot b\right)\equiv d+c-d-\left(c-d\right)\cdot y\cdot b\equiv c\mod b
\]
משפט. יהיו \(a_{1},a_{2},\ldots,a_{n}\in\MKinteger\), מתקיימים שני הפסוקים הבאים:
אם קיים \(r\geq i\in\MKnatural\) כך ש-\(a_{i}\neq0\) אז קיים \(d\in\MKnatural\) יחיד כך ש-\(d\mid a_{i}\) לכל \(n\geq i\in\MKnatural\) ובנוסף לכל \(q\in\MKinteger\) המחלק את כולם (\(q\mid a_{i}\) לכל \(n\geq i\in\MKnatural\)) מתקיים \(q\mid d\).
אם \(a_{i}\neq0\) לכל \(n\geq i\in\MKnatural\) אז קיים \(l\in\MKnatural\) כך ש-\(a_{i}\mid l\) לכל \(n\geq i\in\MKnatural\) ובנוסף לכל \(m\in\MKinteger\) המתחלק בכולם (\(a_{i}\mid m\) לכל \(n\geq i\in\MKnatural\)) מתקיים \(l\mid m\).
הגדרה 1.2. מחלק משותף מקסימלי וכפולה משותפת מינימלית יהיו \(a_{1},a_{2},\ldots,a_{n}\in\MKinteger\),
אם קיים \(n\geq i\in\MKnatural\) כך ש-\(a_{i}\neq0\) אז נסמן ב-\(\gcd\left(a_{1},a_{2},\ldots,a_{n}\right)\) את אותו \(d\) יחיד שמקיים את התנאים במשפט שלעיל, ונקרא לו המחלק המשותף המקסימלי של \(a_{1},a_{2},\ldots,a_{n}\).
אם \(a_{i}\neq0\) לכל \(n\geq i\in\MKnatural\) אז נסמן ב-\(\MKlcm\left(a_{1},a_{2},\ldots,a_{n}\right)\) את אותו \(m\) יחיד שמקיים את התנאים במשפט שלעיל ונקרא לו הכפולה המשותפת המינימלית של \(a_{1},a_{2},\ldots,a_{n}\).
הגדרה 1.3. יהיו \(a,b\in\MKinteger\), נאמר ש-\(a\) ו-\(b\)זרים זה לזה אם \(\gcd\left(a,b\right)=1\) (לפעמים אומרים גם "ראשוניים זה ביחס לזה", אנחנו לא נעשה זאת בגלל הבלבול עם הראשוניים).
הגדרה 1.4. יהיו \(a_{1},a_{2},\ldots,a_{n}\in\MKinteger\), נאמר שהם זרים זה לזה בזוגות אם \(\gcd\left(a_{i},a_{j}\right)\) לכל \(n\geq i,j\in\MKnatural\) כך ש-\(i\neq j\).
הגדרה 1.5. אידיאל קבוצה \(I\subseteq\MKinteger\) תקרא אידיאל אם מתקיימים שלושת התנאים הבאים:
\(0\in I\).
לכל \(a,b\in I\) מתקיים \(a+b\in I\).
לכל \(a\in I\) ולכל \(q\in\MKinteger\) מתקיים \(q\cdot a\in I\).
טענה 1.6. יהיו \(a,b,c\in\MKinteger\), מתקיימים כל הפסוקים הבאים:
אם \(a\mid b\) אז גם \(-a\mid b\) וגם \(a\mid-b\) (ולכן גם \(-a\mid-b\)).
אם \(a\mid b\) ו-\(b\neq0\) אז \(\left|a\right|\leq\left|b\right|\).
אם \(a\mid b\) אז \(a\mid bq\) לכל \(q\in\MKinteger\).
אם \(a\mid b\) וגם \(a\mid c\) אז \(a\mid b+c\)
אם \(a\mid b\) וגם \(a\mid c\) אז \(a\mid bx+cy\) לכל \(x,y\in\MKinteger\).
יחס החלוקה הוא טרנזיטיבי, כלומר אם \(a\mid b\) וגם \(b\mid c\) אז \(a\mid c\).
מתקיים \(a\mid b\) וגם \(b\mid a\) אם"ם מתקיים \(a=\pm b\) (או \(\left|a\right|=\left|b\right|\)).
לכל \(0\neq m\in\MKinteger\) מתקיים \(a\mid b\) אם"ם \(ma\mid mb\).
טענה 1.7. יהיו \(a,b\in\MKinteger\), \(a\) מחלק את \(b\) אם"ם \(\left(b\right)\subseteq\left(a\right)\) ומתקיים שוויון בין \(\left(a\right)\) ל-\(\left(b\right)\) אם"ם \(a=\pm b\).
משפט 1.8. חילוק עם שארית יהיו \(a,b\in\MKinteger\) כך ש-\(0<a\) (כלומר \(a\in\MKnatural\)), קיימים ויחידים \(q,r\in\MKinteger\) כך ש-\(0\leq r<a\) וגם \(b=q\cdot a+r\); בנוסף \(a\mid b\) אם"ם \(r=0\).
הוכחה. נסמן \(q:=\max\left\{ i\in\MKinteger\mid i\cdot a\leq b\right\} \) ו-\(r:=b-q\cdot a\). מהגדרה מתקיים \(q\cdot a+a=\left(q+1\right)\cdot a>b\) ומכאן ש-\(a>b-q\cdot a=r\), כמו כן מהגדרה מתקיים \(r=b-q\cdot a\geq0\) ולכן \(r\) עומד בדרישות; כמובן שמתקיים:\[
b=q\cdot a+r
\]א"כ הוכחנו את הקיום, נוכיח כעת את היחידות. יהיו \(q',r'\in\MKinteger\) כך ש-\(0\leq r'<a\) וגם \(b=q'\cdot a+r'\),\[\begin{align*}
& \Rightarrow q'\cdot a+r'=q\cdot a+r\\
& \Rightarrow\left(q'-q\right)\cdot a+\left(r'-r\right)=0
\end{align*}\]אבל בהכרח מתקיים \(\left|r'-r\right|<a\) ומכאן ש-\(r'-r=0\) וממילא גם \(q'-q=0\), כלומר \(r'=r\) ו-\(q'=q\).
משפט 1.9. יהיו \(a_{1},a_{2},\ldots,a_{n}\in\MKinteger\), מתקיימים שני הפסוקים הבאים:
אם קיים \(r\geq i\in\MKnatural\) כך ש-\(a_{i}\neq0\) אז קיים \(d\in\MKnatural\) יחיד כך ש-\(d\mid a_{i}\) לכל \(n\geq i\in\MKnatural\) ובנוסף לכל \(q\in\MKinteger\) המחלק את כולם (\(q\mid a_{i}\) לכל \(n\geq i\in\MKnatural\)) מתקיים \(q\mid d\).
אם \(a_{i}\neq0\) לכל \(n\geq i\in\MKnatural\) אז קיים \(l\in\MKnatural\) כך ש-\(a_{i}\mid l\) לכל \(n\geq i\in\MKnatural\) ובנוסף לכל \(m\in\MKinteger\) המתחלק בכולם (\(a_{i}\mid m\) לכל \(n\geq i\in\MKnatural\)) מתקיים \(l\mid m\).
טענה 1.10. יהי \(I\subseteq\MKinteger\) אידיאל, קיים \(a\in\MKnatural_{0}\) יחיד כך ש-\(I=\left(a\right)\).
הוכחה. אם \(I=\left\{ 0\right\} \) אז ודאי ש-\(I=\left(0\right)\) ולא קיים \(0\neq a\in\MKnatural_{0}\) כך ש-\(\left(a\right)=I\). א"כ נניח ש-\(I\neq\left\{ 0\right\} \) ונסמן \(a:=\min\left\{ i\in I\mid i>0\right\} \) (מהגדרה \(\left(a\right)\subseteq I\)). יהי \(b\in I\), נחלק את \(b\) ב-\(a\) עם שארית: יהיו \(q,r\in\MKinteger\) כך ש-\(0\leq r<a\) וגם \(b=q\cdot a+r\); \(I\) סגור לכפל בכל שלם ולכן \(-q\cdot a\in I\), \(I\) סגור גם לחיבור ולכן \(r=b-q\cdot a\in I\). מהמינימליות של \(a\) נובע ש-\(r=0\) (אחרת \(0<r\) בסתירה לכך ש-\(a\) הוא החיובי הקטן ביותר שנמצא ב-\(I\)) ולכן \(a\mid b\), כלומר \(b\in\left(a\right)\); \(b\) הנ"ל היה שרירותי ומכאן ש-\(I\subseteq\left(a\right)\), כלומר \(\left(a\right)=I\). היחידות נובעת גם היא מהמינימליות של \(a\): לכל \(a<c\in\MKnatural_{0}\) מתקיים \(a\notin\left(c\right)\) למרות ש-\(a\in I\).
משפט 1.11. לכל \(a,b\in\MKinteger\) כך שלפחות אחד מהם שונה מאפס היוצר של האידיאל \(\left\{ x\cdot a+y\cdot b\mid x,y\in\MKinteger\right\} \) הוא \(\gcd\left(a,b\right)\).
טענה 1.12. יהיו \(a,b\in\MKinteger\).
\(\gcd\left(a,b\right)=\gcd\left(b,a\right)\).
לכל \(m\in\MKnatural\) מתקיים \(m\cdot\gcd\left(a,b\right)=\gcd\left(ma,mb\right)\).
אם קיים \(d\in\MKinteger\) כך ש-\(d\mid a,b\) אז אותו \(d\) מקיים \(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\frac{1}{d}\cdot\gcd\left(a,b\right)\).
לכל \(x\in\MKinteger\) מתקיים \(\gcd\left(a,b\right)=\gcd\left(a,b+ax\right)\).
אם קיים \(c\in\MKinteger\) כך ש-\(c\mid ab\) וגם \(\gcd\left(b,c\right)=1\) אז \(c\mid a\).
1.2 אלגוריתם אוקלידס
יהיו \(n,m\in\MKinteger\) כך שלפחות אחד מהם שונה מאפס, נרצה למצוא את \(\gcd\left(n,m\right)\).
כפי שראינו בטענה1.1המחלקים של מספר שלם ואלו של הנגדי שלו הם אותם מחלקים ולכן הסימן אינו משנה עבור מציאת ה-\(\gcd\), א"כ נגדיר \(r_{0}=\left|n\right|\) ו-\(r_{1}=\left|m\right|\)3כדאי להגדיר את \(r_{0}\) להיות בעל הערך המוחלט הגדול מבין השניים משום שבשלב הראשון של האלגוריתם נחלק את \(r_{0}\) ב-\(r_{1}\) עם שארית. ונמצא את \(\gcd\left(r_{0},r_{1}\right)\).
לאלגוריתם ישנן שתי גרסאות: האלגוריתם הבסיסי והאלגוריתם המורחב, להלן הפירוט של שניהם בפסאודו-קוד.
אלגוריתם אוקלידס הבסיסי
נגדיר \(i:=0\).כל עוד \(r_{i+1}\neq0\):
נחלק את \(r_{i}\) ב-\(r_{i+1}\) עם שארית, נסמן ב-\(q_{i}\) את המנה וב-\(r_{i+2}\) את השארית (כלומר יהיו \(q_{i},r_{i+2}\in\MKinteger\) כך ש-\(0\leq r_{i+2}<r_{i+1}\) וגם \(r_{i}=r_{i+1}\cdot q_{i}+r_{i+2}\)).
נגדיר את \(i\) להיות \(i+1\) ונעבור לשלב הבא בלולאה.
כעת מתקיים \(r_{i+1}=0\), א"כ מתקיים \(r_{i}=\gcd\left(n,m\right)\) ולכן נחזיר את \(r_{i}\) ונסיים.
אלגוריתם אוקלידס המורחב
נגדיר \(i:=0\).נגדיר \({\color{red}a_{-1}:=0}\) ו-\({\color{blue}b_{-1}:=1}\) ומכאן שמתקיים:\[
r_{1}={\color{red}a_{-1}}\cdot r_{0}+{\color{blue}b_{-1}}\cdot r_{1}
\]כל עוד \(r_{i+1}\neq0\):
נחלק את \(r_{i}\) ב-\(r_{i+1}\) עם שארית, נסמן ב-\(q_{i}\) את המנה וב-\(r_{i+2}\) את השארית.
נחלק למקרים:
אם \(i=0\) אז נגדיר \({\color{red}a_{0}:=1}\) ו-\({\color{blue}b_{0}:=-q_{0}}\).
אחרת, נגדיר \({\color{red}a_{i}=a_{i-2}-q_{i}\cdot a_{i-1}}\) ו-\({\color{blue}b_{i}:=b_{i-2}-q_{i}\cdot b_{i-1}}\).
נגדיר את \(i\) להיות \(i+1\) ונעבור לשלב הבא בלולאה.
כעת מתקיים \(r_{i+1}=0\) וגם:\[
\gcd\left(r_{0},r_{1}\right)=r_{i}=a_{i-2}\cdot n+b_{i-2}\cdot m
\]
בעמוד הבא נוכיח את הנכונות של האלגוריתם המורחב וממילא נקבל את הנכונות של האלגוריתם הבסיסי.
הוכחה. נגדיר \(i:=0\). נגדיר \({\color{red}a_{-1}:=0}\) ו-\({\color{blue}b_{-1}:=1}\) ומכאן שמתקיים:\[
r_{1}={\color{red}a_{-1}}\cdot r_{0}+{\color{blue}b_{-1}}\cdot r_{1}
\]כל עוד \(r_{i+1}\neq0\):
נחלק את \(r_{i}\) ב-\(r_{i+1}\) עם שארית, נסמן ב-\(q_{i}\) את המנה וב-\(r_{i+2}\) את השארית.\[
\Rightarrow r_{i+2}=r_{i}-r_{i+1}\cdot q_{i}
\]
#
בכל שלב נובע מסעיף4בטענה האחרונה (1.7) שמתקיים \(\gcd\left(r_{i+2},r_{i+1}\right)=\gcd\left(r_{i+1},r_{i}\right)=\ldots=\gcd\left(r_{0},r_{1}\right)\), וגם \(0\leq r_{i+2}<r_{i+1}\) (לכן האלגוריתם מוכרח להיעצר בשלב כלשהו שהרי מדובר במספרים שלמים).
יהיו \(a_{i},b_{i}\in\MKinteger\) כך שמתקיים:\[
r_{i+2}=a_{i}\cdot r_{0}+b_{i}\cdot r_{i+1}
\]נסביר כיצד למצוא את אותם \(n_{i}\) ו-\(m_{i}\):
אם \(i=0\) אז נגדיר \({\color{red}a_{0}:=1}\) ו-\({\color{blue}b_{0}:=-q_{0}}\) ואכן מתקיים \(r_{2}={\color{red}1}\cdot r_{0}{\color{blue}-q_{0}}\cdot r_{1}\).
אחרת, נזכור ש-\(r_{i+1}=a_{i-1}\cdot r_{0}+b_{i-1}\cdot r_{1}\) וגם \(r_{i}=a_{i-2}\cdot r_{0}+b_{i-2}\cdot r_{1}\), ומכיוון ש-\(r_{i+2}=r_{i}-q_{i}\cdot r_{i+1}\) ניתן להציג את \(r_{i+2}\) כך:\[\begin{align*}
r_{i+2} & =r_{i}-r_{i+1}\cdot q_{i}=\left(a_{i-2}\cdot r_{0}+b_{i-2}\cdot r_{1}\right)-\left(a_{i-1}\cdot r_{0}+b_{i-1}\cdot r_{1}\right)\cdot q_{i}\\
& ={\color{red}\left(a_{i-2}-q_{i}\cdot a_{i-1}\right)}\cdot r_{0}+{\color{blue}\left(b_{i-2}-q_{i}\cdot b_{i-1}\right)}\cdot r_{1}
\end{align*}\]ולכן נגדיר \({\color{red}a_{i}=a_{i-2}-q_{i}\cdot a_{i-1}}\) ו-\({\color{blue}b_{i}:=b_{i-2}-q_{i}\cdot b_{i-1}}\).
נגדיר את \(i\) להיות \(i+1\) ונעבור לשלב הבא בלולאה.
הוכחה. כעת מתקיים \(r_{i+1}=0\), כלומר:\[
0=r_{i+1}=r_{i-1}-r_{i}\cdot q_{i-1}
\]וממילא:\[\begin{align*}
r_{i} & =\gcd\left(r_{i+1},r_{i}\right)=\gcd\left(r_{i},r_{i-1}\right)=\ldots=\gcd\left(r_{0},r_{1}\right)
\end{align*}\]בנוסף מתקיים:\[
\gcd\left(r_{0},r_{1}\right)=r_{i}=a_{i-2}\cdot n+b_{i-2}\cdot m
\]ולכן נחזיר את \(r_{i},a_{i-2},b_{i-2}\) ונסיים.
2 המספרים הראשוניים
2.1 הגדרות
יהי \(0\neq p\in\MKinteger\) כך ש-\(p\neq\pm1\).
הגדרה 2.1. נאמר ש-\(p\) הוא מספר אי-פריק אם אין לו מחלקים שונים מ-\(\pm1\) ו-\(\pm p\), כלומר לכל \(a,b\in\MKinteger\) כך ש-\(p=ab\) מתקיים \(a=\pm p\) (וממילא \(b=\pm1\)) או ש-\(a=\pm1\)(וממילא \(b=\pm p\)).
הגדרה 2.2. נאמר ש-\(p\) הוא מספר ראשוני אם לכל \(a,b\in\MKinteger\) המקיימים \(p\mid ab\) מתקיים \(p\mid a\) או ש-\(p\mid b\).
\(\clubsuit\)
היה קל יותר לו היינו מגדירים את הראשוניים והאי-פריקים כטבעיים גדולים מ-\(1\) המקיימים את התכונות הנ"ל ביחס לטבעיים.
\(\clubsuit\)
בחוג השלמים אלו הגדרות שקולות (נראה זאת בהמשך) אך ישנם חוגים אחרים שבהם המצב שונה.
\(\clubsuit\)
בסיכומי קורס זה אסמן ב-\(\MKprime\) את קבוצת הראשוניים (ב-\(\MKnatural\) או ב-\(\MKinteger\) ע"פ ההקשר).
\(\clubsuit\)
בחוג השלמים האיברים ההפיכים היחידים הם \(\pm1\) אך ישנם חוגים אחרים (למשל חוג הפולינומים4בליניארית2הגדרנו פולינום הפיך אם קיים פולינום אחר כך שמכפלתם היא הפולינום \(1\), לפי זה הפולינומים ההפיכים הם אלו שדרגתם \(0\). וחוג השלמים של גאוס המופיע בהגדרה הבאה) שבהם המצב שונה.
\(\clubsuit\)
הרעיון מאחורי הסימון \(\MKinteger\left[i\right]\) הוא כמו הסימון \(\MKfield\left[x\right]\) שסימן את חוג הפולינומים בעלי מקדמים בשדה \(\MKfield\) אלא שכעת המשתנה אינו \(x\) עלום אלא \(i\), ואכן כל הצבה של \(i\) בפולינום עם מקדמים שלמים ניתן להציג בצורה \(a+bi\); רעיון זה מופיע גם בסימון \(\MKinteger\left[\sqrt{-5}\right]\) שבאחת ההערות בקובץ הטענות.
\(\clubsuit\)
יחס החלוקה, ראשוניות ואי-פריקות מוגדרים בחוג השלמים של גאוס באותה צורה שהוגדרו בשלמים, גם בחוג השלמים של גאוס יש שקילות בין ראשוניות לאי-פריקות ולכן המשפט היסודי של האריתמטיקה תקף גם בו.
\(\clubsuit\)
ניתן להבחין ש-\(\MKord_{p}\left(n\right)\) הוא החזקה שבה הופיע \(p\)5כמובן שהריבוי של \(-p\) זה לזה של \(p\), אם הראשוני אינו מופיע אז הריבוי הוא \(0\). בהצגה:\[
n=\MKsign\left(n\right)\cdot\prod_{i=1}^{r}p_{i}^{e_{i}}
\]כאשר \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) הם מספרים ראשוניים המקיימים \(p_{1}<p_{2}<\ldots<p_{r}\) ו-\(e_{1},e_{2},\ldots,e_{r}\in\MKnatural\).
מה שמייחד מספרים חופשיים מריבועים היא העובדה שכל ראשוני מופיע בפירוק שלהם פעם אחת לכל היותר.
\(\clubsuit\)
\(1\) הוא מספר ריבועי וגם מספר חופשי מריבועים!
הגדרה 2.3. נאמר ששני מספרים \(a,b\in\MKinteger\) הם מספרים חברים7אין לבלבל בין המושג "חברות" (associatedness) למושג "ידידות" של מספרים ידידים (amicable numbers)., אם ניתן להציג את האחד כמכפלה של האחר באיבר הפיך.
הגדרה 2.4. חוג השלמים של גאוס נסמן \(\MKinteger\left[i\right]:=\left\{ a+bi\mid a,b\in\MKinteger\right\} \subseteq\MKcomplex\) ונקרא ל-\(\MKinteger\left[i\right]\)חוג השלמים של גאוס.
הגדרה 2.5. הנורמה (בחוג השלמים של גאוס) היא פונקציה \(N:\MKinteger\left[i\right]\rightarrow\MKnatural_{0}\) המוגדרת ע"י \(N\left(a+bi\right)=a^{2}+b^{2}\)8כלומר הריבוע של הנורמה ב-\(\MKcomplex\), הסיבה לשימוש בריבוע היא כדי להישאר בחוג השלמים..
הגדרה 2.6. הריבוי של מספר ראשוני \(p\in\MKinteger\) בפירוק של מספר שלם \(0\neq n\in\MKinteger\) לראשוניים הוא9נשים לב שמהגדרה הקבוצה \(\left\{ e\in\MKnatural_{0}:p^{e}\mid n\right\} \) אינה ריקה שהרי \(p^{0}=1\mid n\) והיא חסומה מלעיל מפני ש-\(\left|p\right|\geq2\) ולכן קיים \(e\in\MKnatural\) כך ש-\(\left|p^{e}\right|>n\) והרי ערכו המוחלט של המחלק קטן מזה של המחולק.:\[
\MKord_{p}\left(n\right):=\max\left\{ e\in\MKnatural_{0}:p^{e}\mid n\right\}
\]
הגדרה 2.7. מספר שלם \(n\in\MKinteger\) יקרא מספר ריבועי אם קיים \(m\in\MKinteger\) כך ש-\(n=m^{2}\).
הגדרה 2.8. נאמר שמספר שלם \(n\in\MKinteger\)חופשי מריבועים אם לא קיים מספר ריבועי \(1\neq m\in\MKnatural\) כך ש-\(m\mid n\).
הגדרה 2.9. תהא \(\left(M_{n}\right)_{n=1}^{\infty}\) סדרה המוגדרת ע"י \(M_{n}=2^{n}-1\), האיברים בסדרה זו נקראים מספרי מרסן; אם \(M_{n}\) הוא מספר ראשוני נאמר שהוא ראשוני מרסן.
הגדרה 2.10. תהא \(\left(F_{n}\right)_{n=1}^{\infty}\) סדרה המוגדרת ע"י \(F_{n}=2^{n}+1\), האיברים בסדרה זו נקראים מספרי פרמה; אם \(F_{n}\) הוא מספר ראשוני נאמר שהוא ראשוני פרמה.
2.2 התחלה
יהי \(2\leq n\in\MKnatural\), נרצה למצוא את כל המספרים האי-פריקים הקטנים או שווים ל-\(n\). להלן פירוט של אלגוריתם "הנפה של ארטוסתנס" בפסאודו-קוד, אלגוריתם זה מבצע את המשימה (באופן בלתי יעיל בעליל), לאחר הצגתו נסביר מדוע הוא אכן עושה זאת.
נגדיר את \(S\) להיות \(S\setminus\left(a\right)\) (כלומר נסיר מ-\(S\) את כל הכפולות של \(a\) - כולל \(a\)) ואת \(P\) נגדיר להיות \(P\cup\left\{ a\right\} \).
בסיום ריצת הלולאה הקבוצה \(P\) תכיל את כל האי-פריקים הקטנים או שווים ל-\(n\).
\(\clubsuit\)
הסיבה לכך שהאלגוריתם עובד היא שבסיום הריצה כל האיברים ב-\(P\) הם איברים שהוגדרו להיות \(a\) באיזשהו שלב ולכן לא קיים טבעי קטן מהם (שונה מ-\(1\)) המחלק אותם, מכיוון שערכו המוחלט של המחלק מוכרח להיות קטן מזה של המחולק הדבר גורר שכל האיברים ב-\(P\) הם אי-פריקים; מצד שני לכל אי-פריק הקטן או שווה ל-\(n\) אין מחלקים קטנים ממנו ולכן כל אי-פריק כזה נבחר בשלב כלשהו להיות \(a\) וממילא הוא שייך ל-\(P\).
\(\clubsuit\)
טענה זו מראה לנו שניתן לעצור את האלגוריתם לאחר שעוברים את \(\sqrt{n}\) שהרי השורשים של כל המספרים האחרים קטנים מ-\(\sqrt{n}\) ולכן בהכרח אם הם פריקים כבר מחקנו אותם מן הרשימה.
טענה 2.11. לכל \(n\in\MKnatural\) קיים \(m\in\MKnatural\) כך ש-\(m\mid n\) וגם \(m\leq\sqrt{n}\).
2.3 חוג השלמים של גאוס
טענה 2.12. הנורמה ב-\(\MKinteger\left[i\right]\) היא כפלית: לכל \(a,b\in\MKinteger\left[i\right]\) מתקיים \(N\left(ab\right)=N\left(a\right)\cdot N\left(b\right)\).
מסקנה 2.13. האיברים ההפיכים היחידים ב-\(\MKinteger\left[i\right]\) הם \(\pm1\) ו-\(\pm i\).
משפט 2.14. חילוק עם שארית לכל \(a,b\in\MKinteger\left[i\right]\) (כאשר \(b\neq0\)) קיימים \(q,r\in\MKinteger\left[i\right]\) כך ש-\(a=bq+r\) ו-\(N\left(r\right)<N\left(b\right)\).
\(\clubsuit\)
לא למדנו את ההוכחה בתרגול אך גיא אמר שהשיטה היא לחלק את \(a\) ב-\(b\)ללא שארית (כלומר לבצע את החילוק ב-\(\MKcomplex\)) ואז לבחור בתור \(q\) את האיבר הכי קרוב לתוצאה ב-\(\MKinteger\left[i\right]\), זו גם הסיבה לכך שאין כאן יחידות: ייתכן ששניים או ארבעה נמצאים באותו מרחק (אך לא יכולים להיות שלושה בלבד באותו מרחק).
טענה 2.15. למספר ראשוני \(p\in\MKnatural\) יש לכל היותר הצגה אחת כסכום של ריבועים עד כדי שינוי סדר ועד כדי שינוי סימן, כלומר אם ישנן שתי הצגות \(p=a^{2}+b^{2}\) ו-\(p=c^{2}+d^{2}\) (כאשר \(a,b,c,d\in\MKinteger\)) אז מתקיימת אחת משמונה האפשרויות: \(a=\pm c\) ו-\(b=\pm d\) או ש-\(a=\pm d\) ו-\(b=\pm d\)10מבחינה פורמלית הביטוי "\(a=\pm c\) ו-\(b=\pm d\)" אומר פירושו "\(\left(a=c\land b=d\right)\lor\left(a=-c\land b=-d\right)\)", למרות זאת כאן הכוונה היא גם לאפשרויות '\(a=c\land b=-d\)' ו-'\(a=-c\land b=d\)' וכנ"ל לגבי הביטוי "\(b=\pm d\) או ש-\(a=\pm d\)"..
הוכחה. יהי \(p\in\MKnatural\) ראשוני כך שקיימים \(a,b\in\MKinteger\) המקיימים \(a^{2}+b^{2}=p\). יהיו \(s,t,u,v\in\MKinteger\) כך שמתקיים:\[
a=s\cdot u-t\cdot v,\ b=s\cdot v+t\cdot u
\]כלומר:\[
a+b\cdot i=\left(s+t\cdot i\right)\left(u+v\cdot i\right)
\]\[\begin{align*}
\Rightarrow p & =a^{2}+b^{2}=N\left(a+b\cdot i\right)\\
& =N\left(\left(s+t\cdot i\right)\left(u+v\cdot i\right)\right)\\
& =N\left(s+t\cdot i\right)\cdot N\left(u+v\cdot i\right)\\
& =\left(s^{2}+t^{2}\right)\left(u^{2}+v^{2}\right)
\end{align*}\]השוויון \(p=\left(s^{2}+t^{2}\right)\left(u^{2}+v^{2}\right)\) הוא כבר שוויון בשלמים ולכן מאי-הפריקות של \(p\) נובע ש-\(s^{2}+t^{2}=\pm p\) (ו-\(u^{2}+v^{2}=\pm1\)) או ש-\(s^{2}+t^{2}=\pm1\) (ו-\(u^{2}+v^{2}=\pm1\)). נניח בהג"כ ש-\(s^{2}+t^{2}=\pm p\) ו-\(u^{2}+v^{2}=\pm1\), והרי \(0\leq u^{2}+v^{2}\) ולכן בהכרח \(u^{2}+v^{2}=1\); בנוסף ניתן להסיק מכאן ש-\(u=\pm1\) (ו-\(v=0\)) או ש-\(u=0\) (ו-\(v=\pm1\)). נניח בהג"כ ש-\(u=\pm1\) ו-\(v=0\), מכאן ש-\(s=\pm a\) ו-\(t=\pm b\). מכאן ש-\(a+b\cdot i\) הוא מספר אי-פריק ב-\(\MKinteger\left[i\right]\) וממילא גם הצמוד שלו אי-פריק, נזכור שב-\(\MKinteger\left[i\right]\) אי-פריקות שקולה לראשוניות ולכן הם גם ראשוניים. יהיו \(c,d\in\MKinteger\) כך ש-\(c^{2}+d^{2}=p\), \(a\) ו-\(b\) היו שרירותיים ולכן גם \(c+d\cdot i\) והצמוד שלו הם אי-פריקים וראשוניים, בנוסף מתקיים:\[
\left(c+d\cdot i\right)\left(c-d\cdot i\right)=c^{2}+d^{2}=p=a^{2}+b^{2}=\left(a+b\cdot i\right)\left(a-b\cdot i\right)
\]מהראשוניות של \(a+b\cdot i\) נובע ש-\(a+b\cdot i\mid c\pm d\cdot i\) ולכן מאי-הפריקות של \(c\pm d\cdot i\) נובע ש-\(a+b\cdot i=\pm\left(c+d\cdot i\right)\) או ש-\(a+b\cdot i=\pm\left(c-d\cdot i\right)\)11לא ייתכן ש-\(a+b\cdot i\) הוא איבר הפיך מפני שההפיכים היחידים ב-\(\MKinteger\left[i\right]\) הם \(\pm1\) ו-\(\pm i\) ולכן שם \(a+b\cdot i\) היה איבר הפיך היינו מקבלים ש-\(p=1\).; כלומר מתקיים אחד מהשניים: \(a=\pm c\) ו-\(b=\pm d\).
2.4 המשפט היסודי של האריתמטיקה
טענה 2.16. יהי \(p\in\MKinteger\) מספר אי-פריק, ויהי \(I\subseteq\MKinteger\) אידיאל המקיים \(\left(p\right)\subseteq I\), מתקיימת אחת משתי האפשרויות: \(I=\MKinteger\) או ש-\(I=\left(p\right)\).
משפט 2.17. יהי \(p\in\MKinteger\), \(p\) אי-פריק אם"ם \(p\) ראשוני.
\(\clubsuit\)
שקילות זו אינה נכונה בכל חוג והיא נובעת מהיכולת לחלק עם שארית בחוג השלמים, נביא דוגמה לחוג שבו השקילות אינה מתקיימת. נסמן \(\MKinteger\left[\sqrt{-5}\right]:=\left\{ x+y\cdot\sqrt{-5}\mid x,y\in\MKinteger\right\} \subseteq\MKcomplex\)12לשם העניין נגדיר \(\sqrt{-5}:=i\cdot\sqrt{5}\) למרות שבניגוד לשורש הממשי במרוכבים אין דרך להפריד בין \(i\cdot\sqrt{5}\) ל-\(-i\cdot\sqrt{5}\) - הריבוע של שניהם הוא \(-5\) ואין ביניהם חיובי ושלילי כי \(\MKcomplex\) אינו שדה סדור., זהו חוג חילופי (הקורא מוזמן לבדוק זאת) ומתקיים בו:\[
6=2\cdot3=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right)
\]\(2\) הוא אי-פריק בחוג זה13נניח שקיים פירוק \(2=\left(a+b\cdot\sqrt{-5}\right)\left(c+d\cdot\sqrt{-5}\right)\), א"כ:\[
4=\left|2\right|^{2}=2\cdot\overline{2}=\left(a+b\cdot\sqrt{-5}\right)\left(a-b\cdot\sqrt{-5}\right)\left(c+d\cdot\sqrt{-5}\right)\left(c-d\cdot\sqrt{-5}\right)=\left(a^{2}+5b^{2}\right)\left(c^{2}+5d^{2}\right)
\]וזה כבר פירוק ב-\(\MKinteger\), אבל אנחנו יודעים שהפירוק היחיד של \(4\) ב-\(\MKinteger\) ולכן נקבל ש-\(2=a^{2}+5b^{2}\) כעת אם \(b\neq0\) אז \(a^{2}+5b^{2}\geq5>2\) ואם \(b=0\) נקבל שקיים \(a\in\MKinteger\) כך ש-\(a^{2}=2\). אך כפי שניתן לראות בבירור מהפירוק שלעיל הוא אינו ראשוני מפני שהוא מחלק את המכפלה \(\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right)\) אך אינו מחלק אף אחד ממרכיביה14\(\frac{1}{2}\pm\frac{\sqrt{-5}}{2}\notin\MKinteger\left[-5\right]\)..
\(\clubsuit\)
בגלל משפט זה נוכל להתייחס לראשוניות ואי-פריקות כתכונה אחת ולכן בכל פעם שנאמר על מספר שהוא ראשוני נתכוון גם לכך שהמספר אי-פריק.
\(\clubsuit\)
זו אחת הסיבות לכך שאיננו רוצים להגדיר את \(1\) כראשוני, אחרת לא תהיה לנו פריקות חד-ערכית.
\(\clubsuit\)
קל יותר לנסח את המשפט כך: לכל \(0\neq n\in\MKinteger\)15את \(1\) ניתן לייצג באמצעות במכפלה הריקה \(\prod_{i=1}^{0}p_{i}:=1\) ואת \(-1\) באמצעות הנגדי שלה \(-\prod_{i=1}^{0}p_{i}=-1\). קיימת הצגה יחידה בצורה הבאה:\[
n=\MKsign\left(n\right)\cdot\prod_{i=1}^{r}p_{i}^{e_{i}}
\]כאשר \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) הם מספרים ראשוניים המקיימים \(p_{1}<p_{2}<\ldots<p_{r}\) ו-\(e_{1},e_{2},\ldots,e_{r}\in\MKnatural\).
\(\clubsuit\)
שימו לב: בשלב הראשון של ההוכחה (לפני ההגדרה האינדוקטיבית של \(f\)) השתמשנו בתכונת האי-פריקות ובשלב השני השתמשנו בלמה שמבוססת על תכונת הראשוניות, ההוכחה לא הייתה עובדת אלמלא השקילות בין שתי התכונות הללו וכפי שכבר הזכרנו קיימים חוגים שבהם הן אינן שקולות.
\(\clubsuit\)
מכאן נובע שמתקיים גם:\[
\MKlcm\left(a,b\right)=\frac{\left|a\cdot b\right|}{\gcd\left(a,b\right)}
\]שהרי לכל \(r\geq i\in\MKnatural\) מתקיים \(\max\left\{ e_{i},f_{i}\right\} +\min\left\{ e_{i},f_{i}\right\} =e_{i}+f_{i}\).
הוכחה. יהי \(p\in\MKinteger\).
\(\Leftarrow\) נניח ש-\(p\) אי-פריק ויהיו \(a,b\in\MKinteger\) כך ש-\(p\mid ab\). נסמן \(d:=\gcd\left(a,p\right)\), מהגדרה \(d\mid p\) ולכן מהעובדה ש-\(p\) אי-פריק נובע ש-\(d=1\) או ש-\(d=\pm p\). אם \(d=1\) אז \(p\) ו-\(a\) זרים ולכן מסעיף5בטענה 1.7 נובע ש-\(p\mid b\), ואם \(d=\pm p\) אז מהגדרת ה-\(\gcd\)\(p\) מחלק את \(a\).
\(\Rightarrow\) נניח ש-\(p\) ראשוני ויהי \(a\in\MKinteger\) כך ש-\(a\mid p\). יהי \(q\in\MKinteger\) כך ש-\(aq=p\), א"כ מתקיים \(p\mid aq\) ולכן מהראשוניות של \(p\) נובע ש-\(p\mid a\) או ש-\(p\mid q\). אם \(p\mid a\) אז מכיוון שגם \(a\mid p\) נדע ש-\(a=\pm p\) ואם \(p\mid q\) אז מאותה סיבה (\(q\mid p\)) נדע ש-\(q=\pm p\) וממילא \(a=\pm1\).
למה 2.18. יהי \(p\in\MKinteger\) מספר ראשוני ויהיו \(a_{1},a_{2},\ldots,a_{n}\in\MKinteger\) כך שמתקיים \(p\mid a_{1}\cdot a_{2}\cdot\ldots\cdot a_{n}\), קיים \(n\geq i\in\MKnatural\) כך ש-\(p\mid a_{i}\).
משפט 2.19. המשפט היסודי של האריתמטיקה (פריקות חד-ערכית) יהי \(n\in\MKinteger\setminus\left\{ -1,1,0\right\} \), קיימים \(p_{1},p_{2},\ldots p_{r}\in\MKinteger\) ראשוניים יחידים (עד כדי שינוי סדר ועד כדי שינוי סימן) אך לאו דווקא שונים זה מזה כך שמתקיים:\[
n=\prod_{i=1}^{r}p_{i}
\]כלומר אם מתקיים גם \(n=q_{1}\cdot q_{2}\cdot\ldots\cdot q_{s}\) (כאשר \(q_{1},q_{2},\ldots q_{s}\in\MKinteger\) ראשוניים) אז קיימת פונקציה הפיכה \(f:\left\{ i\in\MKnatural\mid i\leq r\right\} \rightarrow\left\{ i\in\MKnatural\mid i\leq s\right\} \) כך שלכל \(r\geq i\in\MKnatural\) מתקיים \(q_{f\left(i\right)}=\pm p_{i}\).
הוכחה. יהי \(n\in\MKinteger\setminus\left\{ -1,1,0\right\} \). ניתן להוכיח באינדוקציה שניתן להציג כל מספר שלם כמכפלה של אי-פריקים16מפרקים לגורמים עד שכבר א"א לחלק מפני שכל הגורמים אי-פריקים., א"כ יהיו \(p_{1},p_{2},\ldots p_{r},q_{1},q_{2},\ldots q_{s}\in\MKprime\) כך שמתקיים:\[
\prod_{i=1}^{r}p_{i}=n=\prod_{j=1}^{s}q_{j}
\]נגדיר פונקציה \(f:\left\{ i\in\MKnatural\mid i\leq r\right\} \rightarrow\left\{ i\in\MKnatural\mid i\leq s\right\} \) באופן אינדוקטיבי. נסמן \(i:=1\)
לכל \(r\geq i\in\MKnatural\):
מהלמה האחרונה נובע שקיים \(s\geq j\in\MKnatural\) כך ש-\(q_{j}=\pm p_{i}\), יהי \(j\) כנ"ל ונסמן \(f\left(i\right):=j\).
כעת נסיר מהמכפלה באגף שמאל את \(p_{i}\) ומאגף ימין נסיר את \(q_{j}\) ושוב נקבל שוויון עד כדי סימן כך ש-\(q_{j}\) כבר אינו מופיע מופיע במכפלה הימנית ומכאן שהפונקציה שנגדיר תהיה חח"ע.
נעבור לשלב הבא בלולאה.
כעת אגף שמאל הוא המכפלה הריקה השווה ל-\(1\) ולכן גם אגף ימין שווה ל-\(1\), כלומר \(s=r\) ומכאן ש-\(f\) על ומכיוון שהיא חח"ע הרי שהיא הפיכה.
למה 2.20. יהיו \(0\neq a,b\in\MKinteger\), נסמן \(n:=ab\) ויהי \(p\in\MKinteger\) מספר ראשוני, מתקיים \(\MKord_{p}\left(a\right)+\MKord_{p}\left(b\right)=\MKord_{p}\left(n\right)\).
טענה 2.21. יהיו \(0\neq a,b\in\MKinteger\), מתקיים \(a\mid b\) אם"ם \(\MKord_{p}\left(a\right)\leq\MKord_{p}\left(b\right)\) לכל \(p\in\MKinteger\) ראשוני.
מסקנה 2.22. יהיו \(0\neq a,b\in\MKinteger\) ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) מספרים ראשוניים ו-\(e_{1},e_{2},\ldots,e_{r},f_{1},f_{2},\ldots,f_{r}\in\MKnatural_{0}\) כך שמתקיים:\[\begin{align*}
a & =\MKsign\left(a\right)\cdot\prod_{i=1}^{r}p_{i}^{e_{i}}\\
b & =\MKsign\left(b\right)\cdot\prod_{i=1}^{r}p_{i}^{f_{i}}
\end{align*}\]במקרה כזה מתקיים:\[\begin{align*}
\gcd\left(a,b\right) & =\prod_{i=1}^{r}p_{i}^{\min\left\{ e_{i},f_{i}\right\} }\\
\MKlcm\left(a,b\right) & =\prod_{i=1}^{r}p_{i}^{\max\left\{ e_{i},f_{i}\right\} }
\end{align*}\]
מסקנה 2.23. יהיו \(0\neq a,b\in\MKinteger\) כך ש-\(a\) חופשי מריבועים ו-\(a\mid b^{2}\), מתקיים גם \(a\mid b\).
משפט 2.24. לכל \(1<n\in\MKnatural\) חופשי מריבועים מתקיים \(\sqrt{n}\notin\MKrational\).
הוכחה. יהי \(1<n\in\MKnatural\) חופשי מריבועים ונניח בשלילה ש-\(\sqrt{n}\in\MKrational\). יהיו \(p,q\in\MKnatural\) כך ש-\(\frac{p}{q}\) היא ההצגה המצומצמת של \(\sqrt{n}\) (כלומר \(\gcd\left(p,q\right)=1\)).\[\begin{align*}
& \Rightarrow\frac{p^{2}}{q^{2}}=\left(\frac{p}{q}\right)^{2}=n\\
& \Rightarrow p^{2}=nq^{2}\\
& \Rightarrow n\mid p^{2}
\end{align*}\]כעת, מכיוון ש-\(n\) חופשי מריבועים נדע שמתקיים \(n\mid p\), א"כ קיים \(k\in\MKnatural\) כך ש-\(nk=p\), יהי \(k\) כנ"ל.\[\begin{align*}
& \Rightarrow n^{2}k^{2}=p^{2}=nq^{2}\\
& \Rightarrow k^{2}n=q^{2}\\
& \Rightarrow n\mid q^{2}
\end{align*}\]ושוב מאותה סיבה נקבל ש-\(n\mid q\), כלומר \(n\) מחלק הן את \(p\) והן את \(q\) בסתירה לכך ש-\(\gcd\left(p,q\right)=1\) ו-\(1<n\). מכאן שהנחת השלילה אינה נכונה ו-\(\sqrt{n}\notin\MKrational\).
מסקנה 2.25. לכל \(n\in\MKnatural\) שאינו מספר ריבועי מתקיים \(\sqrt{n}\notin\MKrational\).
הוכחה. יהי \(n\in\MKnatural\) שאינו מספר ריבועי ויהיו \(a,b,s\in\MKnatural\) כך ש-\(ab=n\), \(b\) חופשי מריבועים, \(a\) הוא מספר ריבועי17ניתן בהכרח לפרק את \(n\) בצורה זו משום שלכל ראשוני \(p\) בפירוק של \(n\) כך ש-\(\MKord_{p}\left(n\right)=1\) "נכניס" ל-\(b\); ועבור כל ראשוני \(q\) בפירוק של \(n\) כך ש-\(\MKord_{q}\left(n\right)\geq2\) "נכניס" את \(q\) בחזקת הזוגי הגדול ביותר שקטן או שווה ל-\(\MKord_{q}\left(n\right)\) ל-\(a\) (נגדיר \(t:=2\cdot\left\lfloor \frac{\MKord_{q}\left(n\right)}{2}\right\rfloor \) ואת \(q^{t}\) "נכניס" ל-\(a\)"), ואת השאר (\(q^{1}\) או \(q^{0}\)) "נכניס" ל-\(b\). ו-\(\sqrt{a}=s\). נשים לב לכך שמתקיים \(\sqrt{n}=\sqrt{ab}=\sqrt{a}\cdot\sqrt{b}=s\cdot\sqrt{b}\), אנחנו יודעים ש-\(s\in\MKrational\) ומהמשפט נובע ש-\(\sqrt{b}\notin\MKrational\), מכאן שגם \(s\cdot\sqrt{b}\notin\MKrational\) שהרי \(\MKrational\) הוא שדה18מהסגירות לחילוק באיבר שונה מאפס נובע שאם \(s\cdot\sqrt{b}\in\MKrational\) אז גם \(\sqrt{b}=\frac{s\cdot\sqrt{b}}{s}\in\MKrational\) (\(s\neq0\) שכן \(s^{2}\cdot b=n\neq0\))..
טענה 2.26. לכל \(0\neq a,b\in\MKinteger\) ולכל \(p\in\MKinteger\) ראשוני מתקיים \(\MKord_{p}\left(a+b\right)\geq\min\left\{ \MKord_{p}\left(a\right),\MKord_{p}\left(b\right)\right\} \).
2.5 שכיחות המספרים הראשוניים
משפט 2.27. קיימים אינסוף ראשוניים, כלומר קבוצת המספרים הראשוניים היא קבוצה אינסופית.
הראשון שהוכיח את המשפט היה אוקלידס, אנחנו נראה שתי הוכחות: הראשונה היא ההוכחה של אוקלידס והיא פשוטה יחסית והאחרת (של אוילר) מערבת כלים כבדים של חשבון אינפיניטסימלי.
הוכחה. הוכחה1- אוקלידס נניח בשלילה שקבוצת הראשוניים היא קבוצה סופית ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKinteger\) כל הראשוניים הללו. נתבונן במספר:\[
a:=1+\prod_{i=1}^{r}p_{i}
\]מהמשפט היסודי של האריתמטיקה יש ל-\(a\) הצגה כמכפלה של ראשוניים ולכן בהכרח קיים ראשוני המחלק אותו, אבל ראשוני כזה אינו יכול להיות אחד מאלו שמופיעים במכפלה שלעיל בסתירה לכך שאלו כל הראשוניים בכלל. מכאן שהנחת השלילה אינה נכונה וקבוצת הראשוניים היא אינסופית.
הוכחה. הוכחה2- אוילר נניח שקבוצת הראשוניים היא קבוצה סופית ויהיו \(p_{1},p_{2},\ldots,p_{r}\in\MKnatural\) כל הראשוניים הטבעיים בקבוצה. ע"פ הנוסחה לסכום של סדרה הנדסית מתכנסת מתקיים:\[
\prod_{i=1}^{r}\frac{1}{1-\frac{1}{p_{i}}}=\prod_{i=1}^{r}\left(\sum_{n=0}^{\infty}\frac{1}{\left(p_{i}\right)^{n}}\right)
\]תהא \(\left(a_{n}\right)_{n=1}^{\infty}\) סדרה המוגדרת ע"י (לכל \(n\in\MKnatural\)):\[
a_{n}:=\prod_{i=1}^{r}\left(\sum_{j=0}^{m_{n}}\frac{1}{\left(p_{i}\right)^{j}}\right)
\]כאשר \(\left(m_{n}\right)_{n=1}^{\infty}\) היא סדרה המוגדרת ע"י \(m_{n}:=\max\left\{ \MKord_{p_{i}}\left(n\right)\mid r\geq i\in\MKnatural\right\} \) לכל \(n\in\MKnatural\), כלומר \(m_{n}\) הוא החזקה הגדולה ביותר שבה ראשוני כלשהו מחלק את \(n\).\[
\Rightarrow\lim_{n\rightarrow\infty}a_{n}=\prod_{i=1}^{r}\left(\sum_{n=0}^{\infty}\frac{1}{\left(p_{i}\right)^{n}}\right)=\prod_{i=1}^{r}\frac{1}{1-\frac{1}{p_{i}}}
\]בנוסף, לכל \(N\in\MKnatural\) ולכל \(N\geq n\in\MKnatural\) ,\(\frac{1}{n}\) מופיע במכפלה:\[
a_{N}:=\prod_{i=1}^{r}\left(\sum_{j=0}^{m_{N}}\frac{1}{\left(p_{i}\right)^{j}}\right)=\sum_{\forall i\leq r:\ 0\leq e_{i}\leq m_{n}}\prod_{i=1}^{r}\frac{1}{\left(p_{i}\right)^{e_{i}}}
\]ומזה נובע שלכל \(N\in\MKnatural\) מתקיים19נזכור שכל האיברים במכפלה חיוביים ושלכל \(N\in\MKnatural\) מתקיים \(m_{N}\leq N\).:\[
a_{N}\geq\sum_{n=1}^{N}\frac{1}{n}
\]כעת נזכור ש-\(\left(a_{n}\right)_{n=1}^{\infty}\) היא סדרה מתכנסת ושהטור ההרמוני הוא טור חיובי ולכן אי-השוויון הנ"ל גורר את התכנסות הטור ההרמוני בסתירה לכך שאנו יודעים שאינו מתכנס. מכאן שהנחת השלילה אינה נכונה וקבוצת הראשוניים היא אינסופית.
\(\clubsuit\)
זוהי הגרסה המפורמלת של ההוכחה שכתב אוילר:\[
\sum_{n=1}^{\infty}\frac{1}{n}=\prod_{p\in\MKprime}\left(\sum_{n=0}^{\infty}\frac{1}{p^{n}}\right)
\]
\(\clubsuit\)
אמנם מבחינה פורמלית זהו סכום אינסופי אך לכל \(k\in\MKnatural\) כך ש-\(\log_{p}n<k\) מתקיים \(\left\lfloor \frac{n}{p^{k}}\right\rfloor =0\).
\(\clubsuit\)
צ'בישב הראה באמצע המאה ה-19ש-\(A=\frac{7}{8}\) ו-\(B=\frac{9}{8}\) מקיימים את הנדרש, בכיתה הוכחנו את המשפט עבור \(A=\frac{1}{2}\cdot\ln2\) ו-\(B=6\cdot\ln2\).
\(\clubsuit\)
בנוסף, צ'בישב הוכיח שאם הגבול \(\begin{alignedat}{1}\lim_{x\rightarrow\infty}\frac{\pi\left(x\right)}{\frac{x}{\ln x}}\end{alignedat}
\) קיים אז הוא שווה ל-\(1\)20כלומר שאם מוכנים לוותר על הדרישה שאי-השוויונות יתקיימו לכל \(1<x\in\MKreal\) ומוכנים להסתפק בדרישה שקיים \(M\in\MKreal\) כך שאי-השוויונות יתקיימו החל מ-\(M\), אז ניתן להשתמש בכל שני קבועים המקיימים \(A<1<B\) (כמובן שככל ש-\(A\) ו-\(B\) יהיו קרובים יותר ל-\(1\) נזדקק ל-\(M\) גדול יותר). אולם ההוכחה של משפט זה, הלא הוא משפט המספרים הראשוניים, נאלצה לחכות עד לשנת1896שאז הוכחה בכלים אנליטיים (אני מנחש שזו הסיבה לכך שמקובל להגדיר את הפונקציה \(\pi\) על \(\left[0,\infty\right)\) ולא על \(\MKnatural\)).
\(\clubsuit\)
החסמים של צ'בישב היו כה טובים עד שאפשרו לו להוכיח לראשונה את נכונותה של השערת ברטראן21ערך בוויקיפדיה: ז'וזף ברטראן. (הנקראת מאז גם "משפט ברטראן-צ'בישב): לכל \(3<n\in\MKnatural\) קיים \(p\in\MKnatural\) ראשוני המקיים \(n\leq p\leq2n\), ההוכחה מסתמכת על משפט צ'בישב ולמעשה ממשפט המספרים הראשוניים נובעת טענה חזקה יותר האומרת שלכל \(0<\varepsilon\in\MKreal\) קיים \(N\in\MKnatural\) כך שלכל \(N<n\in\MKnatural\) יש לפחות ראשוני אחד בקטע \(\left(n,n+\varepsilon\cdot n\right)\).
משפט 2.28. לכל \(n\in\MKnatural\) קיימים שני ראשוניים עוקבים22לכל ראשוני \(q\) שונה מהם מתקיים \(q<p\) או ש-\(p'<q\).\(p,p'\in\MKnatural\) (כך ש-\(p<p'\)) כך ש-\(p'-p>n\), כלומר קיימים מרווחים גדולים כרצוננו בין שני ראשוניים עוקבים.
הוכחה. יהי \(n\in\MKnatural\), נסמן \(m:=n+1\) ונתבונן בסדרת המספרים העוקבים הבאה:\[
\left(m!+2,m!+3,\ldots,m!+m\right)
\]זוהי סדרה באורך \(n\) שכל איבריה פריקים שכן האיבר הראשון מתחלק ב-\(2\), השני ב-\(3\) וכן הלאה עד האיבר האחרון שמחלק ב-\(n+1\).
טענה 2.29. לכל \(n\in\MKnatural\) פריק גם \(M_{n}=2^{n}-1\) (מספר מרסן ה-\(n\)-י) הוא מספר פריק.
הוכחה. יהי \(n\in\MKnatural\) פריק ויהיו \(1<a,b\in\MKnatural\) כך ש-\(a\cdot b=n\).\[\begin{align*}
\Rightarrow M_{n} & =2^{a\cdot b}-1=\left(2^{a}\right)^{b}-1^{b}\\
& =\left(2^{a}-1\right)\cdot\left(2^{0\cdot a}+2^{1\cdot a}+2^{2a}+\ldots+2^{\left(b-1\right)\cdot a}\right)
\end{align*}\]והרי \(a>1\) ולכן הגורם השמאלי גדול מ-\(1\) ו-\(b-1>0\) ולכן הגורם הימני גדול מ-\(1\), כלומר מצאנו פירוק לא טריוויאלי של \(M_{n}\) ועל כן \(M_{n}\) פריק.
טענה 2.30. יהי \(n\in\MKnatural\), אם \(F_{n}=2^{n}+1\) (מספר פרמה ה-\(n\)-י) ראשוני אז קיים \(m\in\MKnatural_{0}\) כך ש-\(n=2^{m}\).
הוכחה. נניח ש-\(F_{n}\) ראשוני, כמו לכל טבעי גם ל-\(n\) קיימים \(m\in\MKnatural_{0}\) ו-\(k\in\MKodd\) כך ש-\(n=2^{m}\cdot k\), יהיו \(m\) ו-\(k\) כנ"ל ונסמן \(u:2^{m}\).\[\begin{align*}
\Rightarrow F_{n} & =2^{u\cdot k}+1=\left(2^{u}\right)^{k}-\left(-1\right)^{k}\\
& =\left(2^{u}-\left(-1\right)\right)\cdot\sum_{j=0}^{k-1}\left(2^{u}\right)^{j}\cdot\left(-1\right)^{k-1-j}\\
& =\left(2^{u}+1\right)\cdot\sum_{j=0}^{k-1}\left(2^{u}\right)^{j}\cdot\left(-1\right)^{k-1-j}
\end{align*}\]כעת, אם \(k>1\) אז \(k-1>1\) (נזכור ש-\(k\) אי-זוגי) ולכן הגורם הימני שונה מ-\(\pm1\) ומכיוון שהגורם השמאלי ודאי שונה מ-\(\pm1\) הרי שמצאנו פירוק לא טריוויאלי של \(F_{n}\) בסתירה להיות \(F_{n}\) אי-פריק, א"כ בהכרח מתקיים \(k=1\), כלומר \(n=2^{m}\cdot k=2^{m}\).
לכל \(x\in\left[0,\infty\right)\) נסמן ב-\(\pi\left(x\right)\) את כמות המספרים הראשוניים בקטע \(\left[0,x\right]\) (כלומר הגדרנו פונקציה \(\pi:\left[0,\infty\right)\rightarrow\MKnatural_{0}\)).
למה 2.31. לכל \(m\in\MKnatural\) מתקיים:\[
1+\sum_{k=1}^{m}\frac{2^{k}}{\ln\left(2^{k}\right)}\leq3\cdot\frac{2^{m}}{\ln\left(2^{m}\right)}
\]
הוכחה. נוכיח את הלמה באינדוקציה על \(m\).
עבור \(m\in\left\{ 1,2,3\right\} \) נשים לב לכך שמתקיים:\[
1<\frac{2}{\ln\left(2\right)}=\frac{2\cdot2}{2\cdot\ln\left(2\right)}=\frac{2^{2}}{\ln\left(2^{2}\right)}
\]ולכן גם:\[
1+\frac{2}{\ln\left(2\right)}<3\cdot\frac{2}{\ln\left(2\right)}
\]וכמו כן גם:\[
1+\frac{2}{\ln\left(2\right)}+\frac{2^{2}}{\ln\left(2^{2}\right)}=1+2\cdot\frac{2}{\ln\left(2\right)}<3\cdot\frac{2}{\ln\left(2\right)}=3\cdot\frac{2^{2}}{\ln\left(2^{2}\right)}
\]בנוסף מתקיים:\[\begin{align*}
1\leq\frac{4}{3\cdot\ln\left(2\right)} & =\frac{4}{3}\cdot\frac{1}{\ln\left(2\right)}=\frac{1}{2}\cdot\frac{2^{3}}{3\cdot\ln\left(2\right)}\\
\frac{2}{\ln\left(2\right)}+\frac{2^{2}}{\ln\left(2^{2}\right)} & =2\cdot\frac{2}{\ln\left(2\right)}=\frac{3}{2}\cdot\frac{2^{3}}{3\cdot\ln\left(2\right)}
\end{align*}\]וממילא:\[
1+\frac{2}{\ln\left(2\right)}+\frac{2^{2}}{\ln\left(2^{2}\right)}+\frac{2^{3}}{\ln\left(2^{3}\right)}\leq3\cdot\frac{2^{3}}{3\cdot\ln\left(2\right)}
\]
כעת יהי \(3\leq m\in\MKnatural\), נניח באינדוקציה שהטענה נכונה עבור \(m\) ונוכיח עבור \(m+1\):\[\begin{align*}
1+\sum_{k=1}^{m+1}\frac{2^{k}}{\ln\left(2^{k}\right)} & =\frac{2^{m+1}}{\ln\left(2^{m+1}\right)}+1+\sum_{k=1}^{m}\frac{2^{k}}{\ln\left(2^{k}\right)}\leq\frac{2^{m+1}}{\ln\left(2^{m+1}\right)}+3\cdot\frac{2^{m}}{\ln\left(2^{m}\right)}\\
& =2\cdot\frac{2^{m}}{\left(m+1\right)\cdot\ln\left(2\right)}+3\cdot\frac{2^{m}}{m\cdot\ln\left(2\right)}\\
& =\frac{2^{m}}{\ln\left(2\right)}\cdot\left(\frac{2}{m+1}+\frac{3}{m}\right)=\frac{2^{m}}{\ln\left(2\right)}\cdot\frac{2m+3m+3}{m\cdot\left(m+1\right)}\\
& \leq\frac{2^{m}}{\ln\left(2\right)}\cdot\frac{2m+3m+3}{m\cdot\left(m+1\right)}\leq\frac{2^{m}}{\ln\left(2\right)}\cdot\frac{6m}{m\cdot\left(m+1\right)}\\
& \leq\frac{2^{m}}{\ln\left(2\right)}\cdot\frac{6}{m+1}=3\cdot\frac{2^{m+1}}{\left(m+1\right)\cdot\ln\left(2\right)}=3\cdot\frac{2^{m+1}}{\ln\left(2^{m+1}\right)}
\end{align*}\]
למה 2.32. לכל \(n\in\MKnatural\) מתקיים:\[
\MKord_{p}\left(n!\right)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor
\]
משפט 2.33. משפט צ'בישב23ערך בוויקיפדיה: פפנוטי צ'בישב. קיימים \(A,B\in\MKreal\) כך ש-\(A<B\) ולכל \(2\leq x\in\MKreal\) מתקיים:\[
A\cdot\frac{x}{\ln x}\leq\pi\left(x\right)\leq B\cdot\frac{x}{\ln x}
\]
הוכחה. נסמן \(A:=\frac{1}{2}\cdot\ln2\) ו-\(B:=6\cdot\ln2\) ונוכיח שלכל \(1<x\in\MKreal\) מתקיים:\[
A\cdot\frac{x}{\ln x}\leq\pi\left(x\right)\leq B\cdot\frac{x}{\ln x}
\]נזכור בכל שלב של ההוכחה שהפונקציה \(\frac{x}{\ln x}\) עולה ממש בתחום \(\left[e,\infty\right)\) ויורדת בתחום \(\left(1,e\right]\). נוכיח תחילה עבור החסם מלעיל (\(B\)). יהי \(n\in\MKnatural\), נסמן \(N:=\begin{pmatrix}2n\\
n
\end{pmatrix}\).\[
\Rightarrow N\leq\sum_{k=0}^{2n}\begin{pmatrix}2n\\
k
\end{pmatrix}=\left(1+1\right)^{2n}
\]\[
\Rightarrow N\leq2^{2n}
\]נסמן \(P:=\left\{ p\in\MKprime\mid n<p\leq2n\right\} \), לכל ראשוני \(p\in P\) מתקיים \(p\mid N\) ו-\(\MKord_{p}\left(N\right)=1\) וזאת משום ש-\(p\) מחלק את המכפלה \(\prod_{i=n+1}^{2n}i\) אך \(p^{2}\) אינו מחלק את המכפלה ובנוסף \(p\) אינו מחלק אף אחד מהאיברים ב-\(n!\).\[\begin{align*}
\Rightarrow\prod_{p\in P}p & \leq N\leq2^{2n}\\
\Rightarrow\sum_{p\in P}\ln\left(p\right) & \leq\ln\left(N\right)\leq\ln\left(2^{2n}\right)=2n\cdot\ln\left(2\right)
\end{align*}\]נניח כרגע ש-\(n>1\),\[\begin{align*}
\Rightarrow\ln\left(n\right)\cdot\left(\pi\left(2n\right)-\pi\left(n\right)\right) & =\ln\left(n\right)\cdot\left|P\right|\leq\sum_{p\in P}\ln\left(p\right)\leq2n\cdot\ln\left(2\right)\\
\Rightarrow\pi\left(2n\right)-\pi\left(n\right) & =\frac{2n\cdot\ln\left(2\right)}{\ln\left(n\right)}=2\cdot\ln\left(2\right)\cdot\frac{n}{\ln n}
\end{align*}\]\(n\) הנ"ל היה שרירותי ולכן הנ"ל נכון לכל \(1<n\in\MKnatural\), בפרט לכל \(k\in\MKnatural\) מתקיים:\[
\pi\left(2^{k+1}\right)-\pi\left(2^{k}\right)=2\cdot\ln\left(2\right)\cdot\frac{2^{k}}{\ln\left(2^{k}\right)}
\]ומכאן ע"פ למה2.21שלכל \(m\in\MKnatural\) מתקיים:\[
\pi\left(2^{m+1}\right)=\sum_{k=0}^{m}\left(\pi\left(2^{k+1}\right)-\pi\left(2^{k}\right)\right)=2\cdot\ln\left(2\right)\cdot\left(1+\sum_{k=1}^{m}\frac{2^{k}}{\ln\left(2^{k}\right)}\right)\leq6\cdot\ln\left(2\right)\cdot\frac{2^{m}}{\ln\left(2^{m}\right)}
\]כעת נשים לב לכך שלכל \(e\leq x\in\MKreal\) קיים \(m\in\MKnatural\) כך ש-\(2^{m}\leq x\leq2^{m+1}\) ולכן עבור אותו \(m\) יתקיים גם:\[
\pi\left(x\right)\leq\pi\left(2^{m+1}\right)\leq6\cdot\ln\left(2\right)\cdot\frac{2^{m}}{\ln\left(2^{m}\right)}\leq6\cdot\ln\left(2\right)\cdot\frac{x}{\ln\left(x\right)}
\]ועבור \(x\in\left(1,e\right)\) מתקיים:\[
\pi\left(x\right)\leq1\leq6\cdot\ln\left(2\right)\cdot e=6\cdot\ln\left(2\right)\cdot\frac{e}{\ln\left(e\right)}\leq6\cdot\ln\left(2\right)\cdot\frac{x}{\ln\left(x\right)}
\]כעת נעבור להוכחה עבור החסם מלרע (\(A\)) ונעבוד אם \(n\in\MKnatural\) כללי שאינו בהכרח גדול ממש מ-\(1\). נזכור שמתקיים \(\begin{pmatrix}2n\\
k
\end{pmatrix}\leq\begin{pmatrix}2n\\
n
\end{pmatrix}\) לכל \(2n\geq k\in\MKnatural_{0}\) .\[
\Rightarrow\sum_{k=1}^{2n-1}\begin{pmatrix}2n\\
k
\end{pmatrix}\leq\begin{pmatrix}2n\\
n
\end{pmatrix}\cdot\left(2n-1\right)
\]ומכאן שגם:\[
\sum_{k=0}^{2n}\begin{pmatrix}2n\\
k
\end{pmatrix}=\begin{pmatrix}2n\\
0
\end{pmatrix}+\sum_{k=1}^{2n-1}\begin{pmatrix}2n\\
k
\end{pmatrix}+\begin{pmatrix}2n\\
2n
\end{pmatrix}=1+\sum_{k=1}^{2n-1}\begin{pmatrix}2n\\
k
\end{pmatrix}+1\leq\begin{pmatrix}2n\\
n
\end{pmatrix}\cdot\left(2n-1\right)+\begin{pmatrix}2n\\
n
\end{pmatrix}=2n\cdot\begin{pmatrix}2n\\
n
\end{pmatrix}
\]\[\begin{align*}
& \Rightarrow\frac{2^{2n}}{2n}=\frac{\left(1+1\right)^{2n}}{2n}=\frac{1}{2n}\cdot\sum_{k=0}^{2n}\begin{pmatrix}2n\\
k
\end{pmatrix}\leq\begin{pmatrix}2n\\
n
\end{pmatrix}=N=\prod_{2n\geq p\in\MKprime}p^{\MKord_{p}\left(N\right)}\\
& \Rightarrow2n\cdot\ln\left(2\right)-\ln\left(2n\right)=\ln\left(\frac{2^{2n}}{2n}\right)\leq\ln\left(\prod_{2n\geq p\in\MKprime}p^{\MKord_{p}\left(N\right)}\right)=\sum_{2n\geq p\in\MKprime}\MKord_{p}\left(N\right)\cdot\ln\left(p\right)
\end{align*}\]נזכור ש-\(N\) הוגדר להיות \(\begin{pmatrix}2n\\
n
\end{pmatrix}=\frac{\left(2n\right)!}{\left(n!\right)^{2}}\) ולכן לכל \(2n\geq p\in\MKprime\) מתקיים:\[
\MKord_{p}\left(N\right)=\MKord_{p}\left(\left(2n\right)!\right)-\MKord\left(\left(n!\right)^{2}\right)=\MKord_{p}\left(\left(2n\right)!\right)-2\cdot\MKord\left(n!\right)
\]ולכן מלמה 2.22 נובע כי (לכל \(2n\geq p\in\MKprime\)):\[
\MKord_{p}\left(N\right)=\sum_{k=1}^{\infty}\left\lfloor \frac{2n}{p^{k}}\right\rfloor -2\cdot\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor =\sum_{k=1}^{\infty}\left(\left\lfloor \frac{2n}{p^{k}}\right\rfloor -\left\lfloor 2\cdot\frac{n}{p^{k}}\right\rfloor \right)
\]לכל \(x\in\MKreal\) מתקיים \(\left\lfloor 2x\right\rfloor -2\cdot\left\lfloor x\right\rfloor \in\left\{ 0,1\right\} \)24אם \(0\leq\left\lfloor x\right\rfloor <\frac{1}{2}\) אז \(\left\lfloor 2x\right\rfloor -2\cdot\left\lfloor x\right\rfloor =0\) ואם \(\frac{1}{2}\leq\left\lfloor x\right\rfloor <1\) אז \(\left\lfloor 2x\right\rfloor -2\cdot\left\lfloor x\right\rfloor =1\)., לכן (לכל \(2n\geq p\in\MKprime\)) כל המחוברים בטור הם \(1\) או \(0\) ובנוסף יש לכל היותר \(\left\lfloor \log_{p}\left(2n\right)\right\rfloor =\left\lfloor \frac{\ln\left(2n\right)}{\ln\left(p\right)}\right\rfloor \) מחוברים שונים מאפס, מכאן שלכל \(2n\geq p\in\MKprime\) מתקיים:\[
\MKord_{p}\left(N\right)\leq\frac{\ln\left(2n\right)}{\ln\left(p\right)}
\]\[
\Rightarrow2n\cdot\ln\left(2\right)-\ln\left(2n\right)\leq\sum_{2n\geq p\in\MKprime}\frac{\ln\left(2n\right)}{\ln\left(p\right)}\cdot\ln\left(p\right)=\sum_{2n\geq p\in\MKprime}\ln\left(2n\right)=\ln\left(2n\right)\cdot\pi\left(2n\right)
\]\[
\Rightarrow\frac{2n}{\ln\left(2n\right)}\cdot\ln\left(2\right)-1\leq\pi\left(2n\right)
\]נניח כעת ש-\(n\geq4\) ונשים לב לכך שמתקיים:\[\begin{align*}
& \left(\frac{2n}{\ln\left(2n\right)}\cdot\ln\left(2\right)-1\right)-\left(\frac{2n+2}{\ln\left(2n+2\right)}\cdot\frac{\ln\left(2\right)}{2}\right)\\
& =\left(\frac{2n}{\ln\left(2n\right)}-\frac{n+1}{\ln\left(2n+2\right)}\right)\cdot\ln\left(2\right)-1\\
& \geq\left(\frac{2n}{\ln\left(2n\right)}-\frac{n+1}{\ln\left(2n\right)}\right)\cdot\ln\left(2\right)-1\\
& \geq\frac{n-1}{\ln\left(2n\right)}\cdot\ln\left(2\right)-1\geq\frac{4-1}{\ln\left(2\cdot4\right)}\cdot\ln\left(2\right)-1\\
& =\frac{3}{\ln\left(2^{3}\right)}\cdot\ln\left(2\right)-1=\frac{3}{3\cdot\ln\left(2\right)}\cdot\ln\left(2\right)-1=0
\end{align*}\]\[
\Rightarrow\frac{2n+2}{\ln\left(2n+2\right)}\cdot\frac{\ln\left(2\right)}{2}\leq\frac{2n}{\ln\left(2n\right)}\cdot\ln\left(2\right)-1\leq\pi\left(2n\right)
\]ושוב \(n\) הנ"ל היה שרירותי ולכן הנ"ל נכון לכל \(4\leq n\in\MKnatural\). לכל \(8\leq x\in\MKreal\) קיים \(n\in\MKnatural\) כך ש-\(2n\leq x\leq2n+2\) ולכן עבור אותו \(n\) יתקיים גם:\[
\frac{x}{\ln\left(x\right)}\cdot\frac{\ln\left(2\right)}{2}\leq\frac{2n+2}{\ln\left(2n+2\right)}\cdot\frac{\ln\left(2\right)}{2}\leq\pi\left(2n\right)\leq\pi\left(x\right)
\]בנוסף, מהעובדה ש-\(\frac{x}{\ln x}\) עולה בקרן \(\left[e,\infty\right)\) נקבל שלכל \(x\in\left[e,3\right)\) מתקיים:\[
\frac{x}{\ln\left(x\right)}\cdot\frac{\ln\left(2\right)}{2}<\frac{4}{\ln\left(2^{2}\right)}\cdot\frac{\ln\left(2\right)}{2}=\frac{4}{2\cdot\ln\left(2\right)}\cdot\frac{\ln\left(2\right)}{2}=1=\pi\left(x\right)
\]ולכל \(x\in\left[3,8\right)\) נקבל שמתקיים:\[
\frac{x}{\ln\left(x\right)}\cdot\frac{\ln\left(2\right)}{2}\leq\frac{8}{\ln\left(8\right)}\cdot\frac{\ln\left(2\right)}{2}=\frac{4}{\ln\left(2^{3}\right)}\cdot\ln\left(2\right)=\frac{4}{3\cdot\ln\left(2\right)}\cdot\ln\left(2\right)<2\leq\pi\left(x\right)
\]כמו כן מהעובדה ש-\(\frac{x}{\ln x}\) יורדת בקטע \(\left[2,e\right]\) נקבל שלכל \(x\in\left[2,e\right)\) מתקיים:\[
\frac{x}{\ln\left(x\right)}\cdot\frac{\ln\left(2\right)}{2}\leq\frac{2}{\ln\left(2\right)}\cdot\frac{\ln\left(2\right)}{2}=1=\pi\left(2\right)\leq\pi\left(x\right)
\]
2.6 העשרה: משפטים והשערות אודות המספרים הראשוניים
\(\clubsuit\)
השערת הראשוניים התאומים: שני ראשוניים עוקבים יקראו תאומים אם ההפרש שלהם הוא \(2\), השערת הראשוניים התאומים טוענת שקיימים אינסוף כאלה וזוהי בעיה פתוחה במתמטיקה; עם זאת בעשור האחרון הצליחו המתמטיקאים Yitang Zhang, James Maynard וטרנס טאו להוכיח שקיימים אינסוף זוגות ראשוניים שהמרווח ביניהם קטן או שווה ל-\(246\)25ז'אנג הוכיח את הטענה עבור \(70\) מליון ולאחר מכן הורידו שני האחרים את החסם ל-\(246\). ראו גם: Twin prime conjecture, Polymath8 (ויקיפדיה האנגלית) והשערת המספרים הראשוניים התאומים (ויקיפדיה העברית).. ממילא קיים מספר \(246\geq n\in\MKnatural\) כך שקיימים אינסוף זוגות ראשוניים שזהו ההפרש שלהם (עיקרון שובך היונים).
\(\clubsuit\)
כמות הראשוניים מהצורה \(4n+1\) וזו של הראשוניים מהצורה \(4n+3\) משתוות אסימפטוטית בשאיפה לאינסוף, כלומר אם נסמן ב-\(f\left(x\right)\) את מספר הראשוניים מהצורה \(4n+1\) שקטנים או שווים ל-\(0\leq x\in\MKreal\) וב-\(g\left(x\right)\) אז כמות הראשוניים מהצורה \(4n+3\) שקטנים או שווים ל-\(0\leq x\in\MKreal\) נקבל:\[
\lim_{x\rightarrow\infty}\frac{f\left(x\right)}{g\left(x\right)}=1
\]
\(\clubsuit\)
משפט דיריכלה26ערך בוויקיפדיה: לז'ן גוסטב פטר יוהאן דיריכלה.: לכל \(a,d\in\MKnatural\) הזרים זה לזה קיימים אינסוף איברים ראשונים שהם איברים בסדרה החשבונית \(\left(a+dn\right)_{n=0}^{\infty}\)27קל מאד להוכיח את הכיוון ההפוך (שאם יש אינסוף ראשוניים בסדרה חשבונית אז הבסיס וההפרש זרים)..
\(\clubsuit\)
משפט גרין-טאו28ערכים בוויקיפדיה: ראו בהערה הבאה.: לכל \(n\in\MKnatural\) קיימת סדרה חשבונית באורך \(n\) שכל איבריה ראשוניים.
\(\clubsuit\)
משפט גרין-טאו-ציגלר29ערכים בוויקיפדיה: בן גרין, טרנס טאו ותמר ציגלר.: לכל ממ"ל במקדמים שלמים שאינה תלויה ליניארית שבה מספר הנעלמים עולה על מספר המשוואות ב-\(2\) (לפחות) יש פתרון בו כל הנעלמים מקבלים ערכים ראשוניים.
\(\clubsuit\)
משפט טאו-ציגלר30ערכים בוויקיפדיה: ראו בהערה הקודמת.: לכל \(P_{1},P_{2},\ldots,P_{n}\in\MKinteger\left[x\right]\) המקיימים \(P_{k}\left(0\right)=0\) לכל \(n\geq k\in\MKnatural\) קיימים אינסוף זוגות \(\left(x,m\right)\in\MKinteger^{2}\) כך ש-\(x+P_{1}\left(m\right),x+P_{2}\left(m\right),\ldots,x+P_{n}\left(m\right)\) כולם ראשוניים.
\(\clubsuit\)
השערת גולדבך31ערך בוויקיפדיה: כריסטיאן גולדבך: לכל \(2<n\in\MKeven\) קיימים שני ראשוניים שסכומם הוא \(n\).
\(\clubsuit\)
הגרסה החלשה של השערת גולדבך32נקראת גם "השערת גולדבך החלשה", "השערת גולדבך האי-זוגית", "השערת גולדבך המשולשת" ו-"בעיית שלושת הראשוניים"; זוהי הגרסה ה"חלשה" משום שהיא נובעת ישירות מהשערת גולדבך עצמה.: לכל \(5<n\in\MKodd\) קיימים שלושה ראשוניים שסכומם הוא \(n\). בשנת2013הוכחה הגרסה החלשה, כמעט אחרי300שנה מאז שהועלתה בהתכתבות בין כריסטיאן גולדבך ללאונרד אוילר, פירוט ניתן למצוא בערך "השערת גולדבך החלשה" (ויקיפדיה).
\(\clubsuit\)
משפטChen33ערך בוויקיפדיה האנגלית: Chen Jingrun.: לכל \(2<n\in\MKeven\) קיימים \(p,q,r\in\MKnatural\) ראשוניים כך ש-\(n=p+q\) או ש-\(n=p+qr\).
רוצים לפרגן לי על בניית האתר וכתיבת הסיכומים? אתם מוזמנים לתת טיפ.פורמטים נוספים:
#scrollButton {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
cursor: pointer;
background-color: #084149;
opacity: 80%;
}
#scrollImage {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
opacity: 80%;
}
function scrollToTop() {
window.scrollTo({ top: 0, behavior: 'smooth' });
}
דפי האתרדף הביתאודותצור קשרמפת אתרענפים מתמטייםהתחלהאנליזהאלגברהענפים נוספיםאקסיומת השלמותסיכומי הרצאות במתמטיקהדף הביתתרומהאודותהקדשהמפת אתרהתחלהאנליזהאלגברהענפים נוספיםצור קשרעודלאתר הקודםsrayaa.comעִבְלִיקְסתנ"ך ברויאר מוקלט
( function() {
var skipLinkTarget = document.querySelector( 'main' ),
sibling,
skipLinkTargetID,
skipLink;
// Early exit if a skip-link target can't be located.
if ( ! skipLinkTarget ) {
return;
}
/*
* Get the site wrapper.
* The skip-link will be injected in the beginning of it.
*/
sibling = document.querySelector( '.wp-site-blocks' );
// Early exit if the root element was not found.
if ( ! sibling ) {
return;
}
// Get the skip-link target's ID, and generate one if it doesn't exist.
skipLinkTargetID = skipLinkTarget.id;
if ( ! skipLinkTargetID ) {
skipLinkTargetID = 'wp--skip-link--target';
skipLinkTarget.id = skipLinkTargetID;
}
// Create the skip link.
skipLink = document.createElement( 'a' );
skipLink.classList.add( 'skip-link', 'screen-reader-text' );
skipLink.href = '#' + skipLinkTargetID;
skipLink.innerHTML = 'לדלג לתוכן';
// Inject the skip link.
sibling.parentElement.insertBefore( skipLink, sibling );
}() );